# -*- coding: utf-8 -*-

# 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组
# 注意：
# 答案中不可以包含重复的四元组

# 示例：
# 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0
# 满足要求的四元组集合为：
# [
#   [-1,  0,  0,  1],
#   [-2, -1,  1,  2],
#   [-2,  0,  0,  2]
# ]

# # 4数求和感觉常规逻辑会很复杂，尝试使用递归的思路解决问题
# # 一个能求任意位数之和的方法，可惜这个算法超时了
# # 算法的复杂度是n的3次方
# class Solution(object):
#     def fourSum(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: List[List[int]]
#         """
#         nums_map = {};
#         for num in nums:
#             if nums_map.has_key(num):
#                 nums_map[num] += 1;
#             else:
#                 nums_map[num] = 1;
#         return self.anySum(nums_map, 4, target);

#     def anySum(self, nums_map, v, target):
#         if not nums_map or v == 0:
#             return [];
#         if v == 1:
#             if nums_map.has_key(target) and nums_map[target] > 0:
#                 return [[target]];
#             else:
#                 return [];
#         nums_map_keys = nums_map.keys();
#         rtn = [];
#         # 深拷贝备份
#         temp_nums_map = {};
#         for key, value in nums_map.items():
#             temp_nums_map[key] = value;

#         for key in nums_map_keys:
#             if temp_nums_map[key] <= 0:
#                 del temp_nums_map[key];
#                 continue;
#             temp_nums_map[key] -= 1;
#             v_less_results = self.anySum(temp_nums_map, v - 1, target - key);
#             if len(v_less_results)==0:
#                 del temp_nums_map[key];
#                 continue;
#             for signal_result in v_less_results:
#                 signal_result.append(key);
#                 rtn.append(signal_result);
#             del temp_nums_map[key];

#         # 优化：之前上面用到temp_nums_map使用的都是nums_map，修改后节省了一个拷贝花费的时间
#         # # 深拷贝复原
#         # for key, value in temp_nums_map.items():
#         #     nums_map[key] = value;
#         return rtn;

# # 使用循环而不使用递归在n的3次方的时间复杂度上通过
# class Solution(object):
#     def fourSum(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: List[List[int]]
#         """
#         nums_map = {};
#         for num in nums:
#             if nums_map.has_key(num):
#                 nums_map[num] += 1;
#             else:
#                 nums_map[num] = 1;
#         nums_map_keys = nums_map.keys();
#         rtn = [];
#         for key in nums_map_keys:
#             nums_map[key] -= 1;
#             if nums_map[key] <= 0:
#                 del nums_map[key];
#             result_3 = self.threeSum(nums_map, target - key);
#             for signal_result in result_3:
#                 signal_result.append(key);
#                 rtn.append(signal_result);
#             if nums_map.has_key(key):
#                 del nums_map[key];
#         return rtn;

#     def threeSum(self, nums_map, target):
#         hash_map = {};
#         for key, value in nums_map.items():
#             hash_map[key] = value;

#         rtn = [];
#         hash_map_keys = hash_map.keys();
#         for i in xrange(0, len(hash_map_keys)):
#             v1_key = hash_map_keys[i];
#             hash_map[v1_key] -= 1;

#             j_begin = 0;
#             if hash_map[v1_key] > 0:
#                 j_begin = i;
#             else:
#                 j_begin = i + 1;

#             already_use_v2_key = [];
#             for j in xrange(j_begin, len(hash_map_keys)):
#                 v2_key = hash_map_keys[j];
#                 hash_map[v2_key] -= 1;

#                 to_find_key = target - v1_key - v2_key;
#                 if to_find_key in already_use_v2_key:
#                     hash_map[v2_key] += 1;
#                     continue;

#                 if hash_map.has_key(to_find_key) and hash_map[to_find_key] > 0:
#                     already_use_v2_key.append(v2_key);
#                     rtn.append([v1_key, v2_key, to_find_key]);

#                 hash_map[v2_key] += 1;
#             del hash_map[v1_key];
#         return rtn;

# 和三数求和一样，也可以先排序然后使用双指针的方法在n的3次方解决此问题
# 因解法有些重复这里就不写了






# 查看评论发现当使用了hash_map是存在n平方的解决方案
# 通过此算法学习到的内容，以及思考解答是思路的盲点
# 1、 去重问题，把四个元素整合成一个tuple然后通过hash_map进行去重，虽然看到立马就懂了，可是实际思考的时候去完全没有考虑到这个地方
# 2、 同样是去重问题，思考过程中一直考虑的是 (题目中有的数目)和(答案中使用到的数目)，通过这2个数值来判断是否对同一个元素过多的重复使用了，完全没有考虑到通过下标进行区分
# 3、 [ nums[i] for i in indexs ]语法糖的句式，简化代码的书写

# 发现的问题：
# 这个算法的时间复杂度还不是n平方
# eg: [1,1,1,1,.....,1], 4
# 在这个例子中 sum = 2 的组合有n平方个
# 然后在
# for index_v1 in sum_2s[v1]:
#     for index_v2 in sum_2s[target - v1]:
#         pass;
# 这个循环中实际上是有n的4次方中组合方式
# 最坏境况下的执行时间应该是n的四次方

# 以下:
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return [];

        ##########################################
        # 当问题中存在解的下标组合越多，这个解法越向最坏情况靠近，因而增加这段代码，排除这种情况
        hash_map = {};
        for num in nums:
            if hash_map.has_key(num):
                hash_map[num] += 1;
            else:
                hash_map[num] = 1;
        nums = [];
        hash_map_keys = hash_map.keys();
        for key in hash_map_keys:
            if hash_map[key] <= 4:
                nums += [key] * hash_map[key];
            else:
                nums += [key] * 4;
        ##########################################

        #求2数和
        sum_2s = {};
        for i in xrange(0, len(nums)):
            for j in xrange(i + 1, len(nums)):
                sum_2 = nums[i] + nums[j];
                if not sum_2s.has_key(sum_2):
                    sum_2s[sum_2] = [];
                sum_2s[sum_2] += [[i, j]];

        #四数和分解为2数和，然后去重复
        rtn = {};
        for v1 in sum_2s:
            if not sum_2s.has_key(target - v1):
                continue;
            for index_v1 in sum_2s[v1]:
                for index_v2 in sum_2s[target - v1]:
                    if index_v1[0] == index_v2[0] or index_v1[0] == index_v2[1] or index_v1[1] == index_v2[0] or index_v1[1] == index_v2[1]:
                        continue;
                    indexs = index_v1 + index_v2;
                    result = [nums[i] for i in indexs];
                    result.sort();
                    rtn[tuple(result)] = 1;
        return [list(key) for key in rtn.keys()];




t = Solution();
print t.fourSum([0] * 100, 0);